#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <string.h>
#include "huffman.h"

typedef long long longtype;
struct CharInfo
{
  unsigned char _ch;
  int _count; //当前字符出现的次数
  string _charcode;//当前字符对应的编码

  CharInfo(const char ch=0)
    :_ch(ch)
     ,_count(0)
  {}
  bool operator!=(const CharInfo& info)
  {
    return _count!=info._count;
  }
  CharInfo operator+(const CharInfo& info)
  {
    CharInfo tmp(_ch);
    tmp._count=_count+info._count;
    return tmp;
    //_count+=info._count;
    //return *this;
  }
  //friend bool operator!=(const CharInfo& info1,const CharInfo& info2)
  //{
  //  return info1._count!=info2._count;
  //}
  //friend CharInfo& operator+(CharInfo& info1,const CharInfo& info2)
  //{
  //  info1._count+=info2._count;
  //  return info1;
  //}
  friend bool operator<(const CharInfo& info1,const CharInfo& info2)
  {
    return info1._count <info2._count;
  }
};
class CompressFile 
{
private:
  CharInfo _arr[256];
  longtype Count;
public:
  
//---------------构造函数进行初始化-----------
//主要工作是将所以字符填充到数组元素的ch字段中
 CompressFile()
 {
   for(int i=0;i<256;i++)
   {
     _arr[i]._ch=i;
     _arr[i]._count=0;
   }
 }
 //--------------统计文件中每个字符出现次数---------
 void CharCount(const char* filename)
 {
   //以二进制形式打开文件，否则将不能读到汉字字符
   cout << filename << endl;
   FILE* fd=fopen(filename,"rb");
   assert(fd);
   unsigned char ch=fgetc(fd);
   while(!feof(fd))
   {
     _arr[ch]._count++;
     ch=fgetc(fd);
     Count++;
   }
   for(int i=0;i<256;i++)
   {
     if(_arr[i]._count!=0)
        cout<<_arr[i]._ch<<":"<<_arr[i]._count<<endl;
   }
 }
 //--------------构建huffman树并求每个字符huffman编码----------------
 void PrintHuffman(HuffmanNode<CharInfo>* root)
 {
    if(root==NULL)
      return;
    cout<<root->_weight._count<<" ";
    PrintHuffman(root->_left);
    PrintHuffman(root->_right);
 }
 void CharHuffmanCode()
 {
   //先以每个字符的出现次数为权值构造一颗huffman树
   Huffman<CharInfo> hm;
   CharInfo invalid;
   hm.MakeHuffman(_arr,256,invalid);
   HuffmanNode<CharInfo>* root=hm.GetRoot();
   PrintHuffman(root);
   cout<<endl;
   GetHuffmanCode(root);
 }
 
 //--------------依次获取每个叶节点的huffman编码---------------
 void GetHuffmanCode(HuffmanNode<CharInfo>* root)
 {
   if(root==NULL)
   {
     return;
   }
   GetHuffmanCode(root->_left);
   GetHuffmanCode(root->_right);
   //寻找叶节点
   if(root->_left==NULL&&root->_right==NULL)
   {
     HuffmanNode<CharInfo>* cur=root;
     HuffmanNode<CharInfo>* parent=cur->_parent;
     string& huffcode=_arr[cur->_weight._ch]._charcode;
     //从叶节点向上走直到跟结点
     while(parent!=NULL)
     {
       //若当前节点是父节点的左孩子，huffman编码加0，否则加1
       if(parent->_left==cur)
         huffcode+='0';
       else 
         huffcode+='1';
       cur=parent;
       parent=cur->_parent;
     }
     //此时得到的该字符的huffman编码是反向的，需要进行逆置
     //huffcode.reserve(huffcode.begin(),huffcode.end());
     reverse(huffcode.begin(),huffcode.end());
     //huffcode.reserve(huffcode.size());
     cout<<huffcode<<endl;
   }
 }

 //---------------------写压缩文件的头部信息-----------------------
 string WriteFileHeader(const string srcfile)
 {

   //将源文件的一些相关信息写入压缩后文件的最前面，便于解压缩
   //txt      还原源文件名
   //4        保存下面有多少行，为了和压缩信息进行区分
   //A:1      保存每个字符出现次数，用于还原huffman树
   //B:3
   //C:5
   //D:7
   
   //获取文件后缀
   //从后往前找第一个出现'.'的位置，并截取后面的字符串保存并写入文件
   size_t index=srcfile.find_last_of('.');
   string filepostfix=srcfile.substr(index);
   //cout<<filepostfix<<endl;
   string header=filepostfix+'\n';
   int linecount=0;//统计有效字符的行数
   char charinfo[1024];
   for(int i=0;i<256;i++)
   {
     if(_arr[i]._count!=0)
       linecount++;
   }
   sprintf(charinfo,"%d\n",linecount);
   header+=charinfo;

   for(int i=0;i<256;i++)
   {
     if(_arr[i]._count!=0)
     {
       sprintf(charinfo,"%c:%d\n",_arr[i]._ch,_arr[i]._count);
       header+=charinfo;
       //charinfo+=_arr[i]._ch;
       //charinfo+=':';
       //itoa(_arr[i]._count,charcount,10);
       //charinfo+=charcount;
     }
   }
   return header;
 }
 //-----------------------------文件压缩---------------------------
 void FileCompress(const char* filename)
 {
   //1.统计文件中各个字符出现的次数
   CharCount(filename);

   //2.根据次数创建huffman树
   //3.求得每个字符的huffman编码
   CharHuffmanCode();

   //4.将文件中的字符都用huffman编码进行表示
   
   //打开源文件
   FILE* fin=fopen(filename,"rb");
   assert(fin);
   //构造目标文件名并打开
   string srcfile=filename;
   string dstfile=srcfile+".comtxt";
   FILE* fout=fopen(dstfile.c_str(),"wb");
   assert(fout);


   //**************************构造压缩文件的头部信息********************************
   string header=WriteFileHeader(srcfile);
   cout<<header<<endl; 
   fwrite(header.c_str(),1,header.size(),fout);


   //*********从源文件中读取字符并将其对应的huffman编码写入目标文件******************
   char sign=0;//每个字符的huffman编码先依次放入该字符中再写入目标文件
   int pos=0;//对写入一个字符的小比特位进行计数，当填充满一个字符时就写入目标文件
   unsigned char ch=fgetc(fin);
   cout<<ch<<endl;
   while(!feof(fin))
   {
     string& code=_arr[ch]._charcode;
     for(size_t i=0;i<code.size();i++)
     {
       pos++;
       sign<<=1;

       //编码为1才填入，为0不用填
       if(code[i]=='1')
         sign|=1;

       //此时填充满了一个字符，该字符写入文件
       if(pos==8)
       {
         cout<<(int)sign<<endl;
         fputc(sign,fout);
         pos=0;
         sign=0;
       }
     }
     //处理完一个字符，再去获取新字符
     ch=fgetc(fin);
   }
   //此时读完了源文件但可能还有部分编码未写满一个字符，也未写入目标文件
   //处理该情况，将低位移动到高位，再写一次文件
   if(pos!=0)
   {
     sign<<=(8-pos);
     cout<<(int)sign<<endl;
     fputc(sign,fout);
   }
   fclose(fout);
   fclose(fin);

 }

///////////////////////////////////////////////////////
// 解压缩文件
///////////////////////////////////////////////////////


void UnFileCompress(string srcfile)
{
  //1.解析压缩文件的头部信息
  
  //**********读取文件后缀**********
  FILE* fsrc=fopen(srcfile.c_str(),"rb");
  assert(fsrc);

  //保存压缩前的文件后缀
  string filepostfix;
  char ch=fgetc(fsrc);
  while(ch!='\n')
  {
    filepostfix+=ch;
    ch=fgetc(fsrc);
  }

  //和压缩文件的路径进行拼接，构造压缩前的文件名
  size_t pos=srcfile.find_last_of('.');
  string dstfile=srcfile.substr(0,pos);
  FILE* fdst=fopen(dstfile.c_str(),"wb");
  cout<<dstfile<<endl;
  
  //*******************读取有效字符行数************
  string line;
  ch=fgetc(fsrc);
  while(ch!='\n')
  {
    line+=ch;
    ch=fgetc(fsrc);
  }
  //用来保存后面要读取得行数
  int linecount=atoi(line.c_str());
  cout<<linecount<<endl;

  //********解析出有效字符分别在文件中出现的次数***********
  for(int i=0;i<linecount;i++)
  {
    line.clear();
    ch=fgetc(fsrc);
    while(ch!='\n')
    {
      line+=ch;
      ch=fgetc(fsrc);
    }
    //!!!!!!!!!!!!!!!!!!
    //!!!!!!!!!!!!!!!!!!
    if(line.empty())
    {
      line+='\n';
      ch=fgetc(fsrc);
      while(ch!='\n')
      {
        line+=ch;
        ch=fgetc(fsrc);
      }
    }
    //将各字符出现次数保存在数组对应位置
    _arr[(unsigned char)line[0]]._count=atoi(line.c_str()+2);
  }

  //用于调试的日志
   for(int i=0;i<256;i++)
   {
     if(_arr[i]._count!=0)
        cout<<_arr[i]._ch<<":"<<_arr[i]._count<<endl;
   }
  
  //2.根据字符出现次数构建huffman树
  Huffman<CharInfo> hm;
  CharInfo invalid;
  hm.MakeHuffman(_arr,256,invalid);
  PrintHuffman(hm.GetRoot());

  //3.读取压缩信息并根据huffman树转成对应字符写入文件
  //
  //先要求压缩前文件的大小，避免在解压时将压缩文件中最后一个字符未
  //未填充的部分（0）当作压缩信息一块解压出来导致出错
  //这里的文件大小刚刚好就是huffman树根节点权值对应的数字
  HuffmanNode<CharInfo>* root=hm.GetRoot();
  int filesize=root->_weight._count;

  HuffmanNode<CharInfo>* cur=root;
  ch=fgetc(fsrc);
  while(!feof(fsrc))
  {
    for(int i=0;i<8;i++)
    {
      if( (ch>>(7-i))&1 )
      {
        cur=cur->_right;
      }
      else 
      {
        cur=cur->_left;
      }
      //走到叶节点，将该节点对应字符写入文件，再将当前节点置为根结点的位置
      if(cur->_left==NULL&&cur->_right==NULL)
      {
        char c=cur->_weight._ch;
        fputc(c,fdst);
        cur=root;
        filesize--;
      }
      //当文件大小被减为0时说明解析完毕
      if(filesize==0)
      {
        break;
      }
    }
    //解析完一个字符（8bit），再去获取后序字符
    ch=fgetc(fsrc);
  }
  fclose(fsrc);
  fclose(fdst);
}
};


///////////////////////////////////////////////////////
// 测试压缩文件
///////////////////////////////////////////////////////

void TestFileCompress(const char *file)
{
  CompressFile comp;
  comp.FileCompress(file);
}


///////////////////////////////////////////////////////
// 测试解压缩文件
///////////////////////////////////////////////////////

void TestFileUncompress(const char *file)
{
  CompressFile comp;
  comp.UnFileCompress(file);
}
